#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
#include <string>
#include <memory>
#include <functional>
#include <algorithm>
#include <thread>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

struct PCB {
    std::string pid_name;   // 进程标识
    char state;             // 进程当前状态
    int priority;           // 进程优先级
    int neededTime;         // 进程运行需要的时间
    int arrivalTime;        // 进程到达的时间
    int usedTime;           // 累计运行时间
    int totalWaitTime;      // 进程等待CPU时间的总和
    bool isUpdate;          // 用于记录当前进程的等待时间是否更新

    PCB(const std::string& pname, char pstate, 
        int ppriority, int pneedTime, int parrival, int ptotaltime = 0)
        : pid_name(pname),
          state(pstate),
          priority(ppriority),
          neededTime(pneedTime),
          arrivalTime(parrival),
          totalWaitTime(ptotaltime),
          isUpdate(false)
    {}
};

struct Rqueue {
    int number;             // 队列的标号
    int priority;           // 队列优先级
    int timeSlice;          // 队列时间片长度
    std::vector<PCB> q;      // 存放进程的队列

    using ptr = std::shared_ptr<Rqueue>;

    Rqueue(int ptime, int ts, int num)
        : priority(ptime),
          timeSlice(ts),
          number(num)
    {}
};

class MultiLeveledFeedback {
private:
    const static int pcb_num = 20;
    // 对sem进行P操作，占用一个信号量
    void P_sem(sem_t& sem) {
        sem_wait(&sem);
    }

    // 释放一个信号量，信号量加加
    void V_sem(sem_t& sem) {
        sem_post(&sem);
    }

    bool isEmpty(std::vector<Rqueue::ptr>& list_queue) {
        for (auto& queue : list_queue) {
            if (!queue->q.empty())
                return false;
        }
        return true;
    }

    void* generator(void* args) {
        std::vector<Rqueue::ptr>* list_queue_ptr = static_cast<std::vector<Rqueue::ptr>*>(args);
        int count = pcb_num;

        static int pnum = 0;

        while (count--) {

            // 好需要进行获取信号量
            P_sem(sem_mutex);

            // 创建线程
            int needTime = rand() % 199 + 2;
            int arrivalTime = rand() % 199 + 2;
            std::string pname = "Process " + std::to_string(pnum++);
            PCB pcb(pname, 'r', 1, needTime, arrivalTime);
            
            std::cout << "Generator:" << pname << " is generated, neededTime = " 
                << needTime << ", arrivalTime = " << arrivalTime << std::endl;
            // 将线程加入到队列中
            auto it = list_queue_ptr->begin();
            std::cout << "duilie" << std::endl;
            (*it)->q.push_back(pcb);
            std::cout << "ssss" << std::endl;

            

            int sleep_time = rand() % 100 + 1;
            std::cout << "Generator: Sleep for " << sleep_time 
                << "ms after generatint next new process" << std::endl;
            // 现在释放信号量
            V_sem(sem_cond);
            // 休眠时间
            std::this_thread::sleep_for(std::chrono::microseconds(sleep_time));
        }
        return nullptr;
    }

    bool executor(std::vector<Rqueue::ptr>& list_queue, int index) {
        Rqueue::ptr q = *(list_queue.begin() + index);
        // 获取队首元素，删除队首元素
        PCB& pcb = q->q.front();
        int consumeTime = pcb.neededTime > q->timeSlice ? q->timeSlice : pcb.neededTime; 
        std::cout << "Executor: " << pcb.pid_name << " in queue " << q->number 
            << " consumes " << consumeTime << " ms" << std::endl;
        
        if (currentTime < pcb.arrivalTime)
            currentTime = pcb.arrivalTime;
        // 更新pcb的等待时间
        if (pcb.isUpdate == false) 
            pcb.totalWaitTime = currentTime - pcb.arrivalTime; 

        // 更新当前的时间
        currentTime += pcb.neededTime;

        if (pcb.neededTime > q->timeSlice) {
            // 需要的时间大于当前队列的时间，减去时间之后，放到下一个队列去
            pcb.neededTime -= q->timeSlice;
            return false;
        }
        return true;
    }

    void* scheduler(void* args) {
        std::vector<Rqueue::ptr>* list_queue_ptr = static_cast<std::vector<Rqueue::ptr>*>(args);
        int count = pcb_num;
        while (true) {
            // 获取信号
            P_sem(sem_cond);
            // 若此时队列为空，则直接退出
            if (isEmpty(*list_queue_ptr))
                break;

            for (auto& q : *list_queue_ptr) {
                if (q->q.empty()) continue;
                // 调用executor去执行函数
                PCB& pcb = q->q.front();
                bool ret = executor(*list_queue_ptr, q->number);
                if (ret == false) {
                    std::cout << "Scheduler: " << pcb.pid_name << " is moved to queue " 
                        << q->number + 1 << " , priority = " << q->number + 2 << std::endl;  
                    // 然后将数据放到下一个队列中去
                    q->q.erase(q->q.begin());
                    auto it = list_queue_ptr->begin() + q->number + 1;
                    (*it)->q.push_back(pcb);
                } else {
                    std::cout << "Scheduler: " << pcb.pid_name 
                        << " finished, total waiting time = " << pcb.totalWaitTime << std::endl;
                    totaltime += pcb.totalWaitTime;
                }
                break;
            }

            for (auto& q : *list_queue_ptr) {
                std::cout << "Queue " << q->number << ":";
                for (auto& pcb : q->q) 
                    std::cout << pcb.pid_name << " ";
                std::cout << std::endl;
            }
            // 释放信号量
            V_sem(sem_mutex);
        }
        return nullptr;
    }

public:
    MultiLeveledFeedback(pthread_t t1, pthread_t t2) 
        : generator_t(t1),
          scheduler_t(t2),
          currentTime(0),
          totaltime(0)
    {
        sem_init(&sem_mutex, 0, 1);
        sem_init(&sem_cond, 0, 0);
    }

    void createReadyQueue(std::vector<Rqueue::ptr>& list_queue) {
        // 创建五个就绪队列
        int timeSlice = 10;
        int index = 0;
        for (int i = 5; i >= 1; i--) {
            Rqueue::ptr rq = std::make_shared<Rqueue>(i, timeSlice, index++);
            list_queue.push_back(rq);
            timeSlice *= 2;
        }
    }

    void deleteReadyQueue(std::vector<Rqueue::ptr>* list_queue) {
        delete list_queue;
    }

    void start(void* args) {
        auto Generator = [](void* arg) -> void* {
            return static_cast<MultiLeveledFeedback*>(arg)->generator(arg);
        };
            // std::cout << "xxxxx" << std::endl;

        pthread_create(&generator_t, nullptr, Generator, args);

        auto Scheduler = [](void* arg) -> void* {
            return static_cast<MultiLeveledFeedback*>(arg)->scheduler(arg);
        };
        pthread_create(&scheduler_t, nullptr, Scheduler, args);
    }

    void join() {
        pthread_join(generator_t, nullptr);
        pthread_join(scheduler_t, nullptr);

        float ave_time = static_cast<float>(totaltime) / pcb_num;
        std::cout << "Average waiting time is " << ave_time << std::endl;
    }

    ~MultiLeveledFeedback() {
        sem_destroy(&sem_mutex);
        sem_destroy(&sem_cond);
    }

private: 
    sem_t sem_mutex;
    sem_t sem_cond;
    pthread_t generator_t;
    pthread_t scheduler_t;
    int totaltime;
    int currentTime;
};


int main() {
    srand(time(0));
    std::vector<Rqueue::ptr>* list_queue = new std::vector<Rqueue::ptr>;
    pthread_t t1, t2;
    MultiLeveledFeedback mul(t1, t2);
    mul.createReadyQueue(*list_queue);

    mul.start(list_queue);
    mul.join();

    mul.deleteReadyQueue(list_queue);
    
    return 0;
}